语法分析器生成器

这里有我自己编写的LALR生成器，仅供参考

naturerun/LALRAnalysisGenerator

该生成器读入指定文件中的文法描述，自动生成LALR(1)自动机和语法分析表，如果有移入归约或归约归约冲突会自动报错，生成的语法分析信息保存在指定的输出文件里

其中我对龙书中LALR(1)闭包生成算法进行了适当的优化，提升生成效率。另外对first集和follow集生成算法进行了有别于传统形式的大幅改进以提升生成效率，first集和follow集生成算法不是网上出现的递归算法，因为递归算法在处理推导出的符号串直接或间接地包含自身的非终结符号时会陷入无限递归导致堆栈溢出，同时也和简单迭代到不动点的迭代算法有很大的不同，完全采用了不同的思路对算法进行了改进和优化。另外其中还提供了计算firstK和followK的算法,firstK指非终结符或文法符号串能够推导出的前K个终结符号的集合的集合，followK指在某个句型中跟在给定非终结符号后的前K个终结符的集合的集合，设计以上算法的目的是为构造LR(k)生成器和实现LL(k)分析算法提供工具，这里为了提升firstK集和followK集的查找效率，firstK和followK全部以string形式保存在TrieTree(前缀树)中，TrieTree由我自己实现，目的是对其做适当改进以适应当前问题的需要

值得一提是，最近接触到了GLR算法，它是在LR的基础上对LR算法的改进，能够处理有歧义的上下文无关文法。由于GLR分析表实际上是简单地把LR算法中所有有冲突的移入归约动作全部保存在语法分析表表项中，并在分析中尝试有歧义的分析动作生成沿不同的分析路径生成多棵不同的语法树，所以理论上对以上程序进行少许改进就能生成GLR分析表，有了语法分析表的支持实际的GLR分析过程就可以另外写代码实现了

项目中的代码仅供参考，每个人都有自己不同于他人的思考方式，编程风格和解决问题的方法，所以以上代码所起的帮助作用不会很大

提示：阅读本文需掌握编译原理的相关基础知识

本文中使用C++语言系统地实现了龙书中LALR(1)语法分析表的构造算法,首先计算增广文法的LR(0)项集族，每一个项集只包含内核项，计算过程中自动生成了LR(0)自动机,该自动机使用基于十字链表存储结构的有向图表示。然后通过确定自发生成和传播的向前看符号算法计算各LR(0)内核项集自发生成的向前看符号(增广文法新增产生式的向前看符号不包括在内)并确定LR(0)内核项集之间向前看符号的传播关系。最后一遍扫描前将为增广文法新增产生式添加向前看符号即输入结束符$，然后传播向前看符号直到不能传播为止，扫描结束后就生成了LALR(1)内核项集族。随后调用函数计算各LALR(1)项集的非内核项集确定LALR(1)项集族，并得到LALR(1)自动机。最后根据LALR(1)自动机填写LALR(1)语法分析表完成语法分析表的生成工作。

程序测试用例为博主自行编写的正则表达式文法(文法部分地方写得较别扭，而且并非反映正则表达式全部特性的文法，对正反向预查的支持存在一些问题，请读者见谅)，由于文法保存在文本中，需要由计算机读入分析，为了便于计算机理解需要将书写格式标准化,博主自行设计了书写格式，具体如下：

#1b 非终结符 非终结符 ---- #1e （非终结符号集合）

#2b 终结符 终结符 —- #2e （终结符号集合）

#3b 增广文法开始符号 原文法开始符号 #3e

#4b

#b 非终结符(产生式头) $1($2) 非终结符或终结符 $1($2) 非终结符或终结符 —- #e (产生式体) （$1标志非终结符，$2标志终结符，第一个产生式必须为增广产生式，第二个产生式必须为原文法以原文法开始符号为头的产生式）

#4e

其中省略号表示相同格式子项的重复出现，按照以上格式书写的文法(该文法修改了无数遍，说多了都是泪)为：

#1b S’ S preSurvey E T M F G outSquare B V C B’ inSquare inSquareRange #1e

#2b \ SPECTRANMETA POSITIVE-SURE-PRE POSITIVE-NEGA-PRE NEGATIVE-SURE-PRE NEGATIVE-NEGA-PRE ) | CLOSURE ? GIVEN LBOUND ULBOUND CLOSURE-NONGREEDY LBOUND-NONGREEDY ULBOUND-NONGREEDY CAP NONPRECAP SPECTRAN TRANMETA UPPERALPHA LOWERALPHA DIGIT SPECMETA REVERSEREF ^ [ ] - OTHERMETA $ #2e

#3b S’ S #3e

#4b

#b S’ $1 S #e

#b S $1 E #e

#b S $1 preSurvey #e

#b preSurvey $1 E $2 POSITIVE-SURE-PRE $1 E $2 ) #e

#b preSurvey $1 E $2 POSITIVE-NEGA-PRE $1 E $2 ) #e

#b preSurvey $2 NEGATIVE-SURE-PRE $1 E $2 ) $1 E #e

#b preSurvey $2 NEGATIVE-NEGA-PRE $1 E $2 ) $1 E #e

#b E $1 E $2 | $1 T #e

#b E $1 T #e

#b T $1 T $1 M #e

#b T $1 M #e

#b M $1 M $2 CLOSURE #e

#b M $1 M $2 ? #e

#b M $1 M $2 GIVEN #e

#b M $1 M $2 LBOUND #e

#b M $1 M $2 ULBOUND #e

#b M $1 M $2 CLOSURE-NONGREEDY #e

#b M $1 M $2 LBOUND-NONGREEDY #e

#b M $1 M $2 ULBOUND-NONGREEDY #e

#b M $1 F #e

#b F $2 CAP $1 E $2 ) #e

#b F $1 G #e

#b F $2 NONPRECAP $1 E $2 ) #e

#b F $1 outSquare #e

#b outSquare $2 SPECTRAN #e

#b outSquare $2 TRANMETA #e

#b outSquare $2 \ #e

#b outSquare $2 SPECTRANMETA #e

#b outSquare $2 UPPERALPHA #e

#b outSquare $2 LOWERALPHA #e

#b outSquare $2 DIGIT #e

#b outSquare $2 SPECMETA #e

#b outSquare $2 REVERSEREF #e

#b outSquare $2 ^ #e

#b G $2 [ $1 B $1 V $1 C $2 ] #e

#b V $2 ^ #e

#b V #e

#b B $1 B $1 B’ #e

#b B $1 B’ #e

#b B’ $1 V $1 inSquareRange $2 - $1 inSquareRange #e

#b inSquareRange $2 SPECTRAN #e

#b inSquareRange $2 SPECMETA #e

#b inSquareRange $2 OTHERMETA #e

#b inSquareRange $2 UPPERALPHA #e

#b inSquareRange $2 LOWERALPHA #e

#b inSquareRange $2 DIGIT #e

#b inSquareRange $2 CLOSURE #e

#b inSquareRange $2 \ #e

#b inSquareRange $2 SPECTRANMETA #e

#b inSquareRange $2 ? #e

#b inSquareRange $2 CAP #e

#b inSquareRange $2 | #e

#b inSquareRange $2 ) #e

#b C $1 C $1 inSquare #e

#b C $1 inSquare #e

#b inSquare $1 inSquareRange #e

#b inSquare $2 NONPRECAP #e

#b inSquare $2 POSITIVE-SURE-PRE #e

#b inSquare $2 POSITIVE-NEGA-PRE #e

#b inSquare $2 NEGATIVE-SURE-PRE #e

#b inSquare $2 NEGATIVE-NEGA-PRE #e

#b inSquare $2 ULBOUND #e

#b inSquare $2 LBOUND #e

#b inSquare $2 ULBOUND-NONGREEDY #e

#b inSquare $2 LBOUND-NONGREEDY #e

#b inSquare $2 CLOSURE-NONGREEDY #e

#b inSquare $2 GIVEN #e

#b G $2 [ $1 B $2 ] #e

#b G $2 [ $1 V $1 C $2 ] #e

#4e

#1b和#1e之间的部分为文法非终结符,#2b和#2e之间的部分为文法终结符,S’为增广文法开始符,S为原文法开始符

#4b和#4e之间的部分为产生式,紧跟于#b之后的是产生式头,随后为产生式体, $2表示紧跟其后的文法符号为终结符,$1表示紧跟其后的文法符号为非终结符，所有这些构成了对上下文无关文法的完整描述。这里非终结符、终结符以及产生式的含义博主会在将来发布的有关构建正则表达式引擎的文章中详解，现在只需着眼于文法本身，不必关心它们的具体含义。

需要另外说明的是，文法设计不当会导致一些异常现象的发生，例如如果把以上文法第三道产生式的产生式头的非终结符S改为F(这样就允许了预查表达式任意的自嵌套)，程序会在计算follow集时陷入死循环，原因是修改过的文法第6，7道产生式直接导致程序在计算出非终结符E的follow集前必须先计算出E的follow集，导致循环计算，这样计算follow集时会陷入死循环。可以验证，如果去掉产生式6、7程序就可以正常运行并输出结果(但是存在语法分析动作冲突)。

下面贴出代码

代码清单(C++):

见github 地址 GitHub - naturerun/LALRAnalysisGenerator: 完整的LALR(1)分析算法,从first follow集计算，闭包生成到向前看为符号传播,LALR(1)自动机生成,语法分析表生成一应俱全

注意，这里有两个头文件Priority_Queue.h和assistfunction.h。Priority_Queue.h存放的是博主自己实现的优先级队列类，之所以没有使用标准库提供的容器适配器是因为适配器实现的优先级队列缺少一些操作队列成员的必要方法，如以下代码中的begin(),end()且容器适配器提供的接口的调用约定和返回值不符号程序编写要求，此外优先级队列是用堆实现的，但计算LALR闭包的算法要求优先队列必须用数组实现，其成员按优先级从小到大排序，故楼主自行实现了优先级队列。Priority_Queue.h代码如下：

————————————————

头文件assistfunction.h中定义了一些算法需要使用的辅助例程(只有第一个函数和算法有关，其他例程用于正则表达式引擎，后续会解读)，由于代码简洁易懂，不是很重要，这里就不详细解说了。